#include <iostream>
#include <queue>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

struct edge{
	int stop,len;
};

struct node{
	int index,time;
};


bool cmp(node a,node b){
	return a.time<b.time;
}


int main(){
	int n,m;
	cin>>n>>m;
	node vil[n];
	bool build[n];
	memset(build,false,sizeof(build));
	vector<edge> e[n];
	for(int i=0;i<n;i++){
		cin>>vil[i].time;
		vil[i].index = i;
	}
	sort(vil,vil+n,cmp);
	int dis[n][n];
	memset(dis,-1,sizeof(dis));
	for(int i=0;i<m;i++){
		int s,t,l;
		cin>>s>>t>>l;
		e[s].push_back({t,l});
		e[t].push_back({s,l});
	}
	
	int index=0;
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		int x,y,t;
		cin>>x>>y>>t;
		while(index < n  &&  vil[index].time <= t){
			int k=vil[index].index;
			dis[k][k] = 0;
			build[k] = true;
			queue<int> q;
			q.push(k);
			for(int a=0;a<e[k].size();a++){
//				if(dis[e[k][a].stop][k] == -1  ||  dis[e[k][a].stop][k] > e[k][a].len)
				if(build[e[k][a].stop]){
					dis[e[k][a].stop][k] = dis[k][e[k][a].stop] = e[k][a].len;
					q.push(e[k][a].stop);
				}
			}
			while(!q.empty()){
				k = q.front();
				q.pop();
				for(int a=0;a<n;a++){
					for(int b=0;b<n;b++){
						if(a == b  ||  b == k  ||  k == a)
							continue;
						if(dis[a][k] == -1  ||  dis[k][b] == -1)
							continue;
						if(dis[a][b] == -1  ||  dis[a][b] > dis[a][k]+dis[k][b])
							dis[a][b] = dis[a][k]+dis[k][b];
					}
				}
			}
			
//			cout<<endl<<"[i]"<<i<<" [index]"<<index<<endl;
//			for(int a=0;a<n;a++){
//				for(int b=0;b<n;b++){
//					cout<<dis[a][b]<<" ";
//				}
//				cout<<endl;
//			}
			index++;
		}
		cout<<dis[x][y]<<endl;
	}
	return 0;
}
